package alogrithm;

import java.util.ArrayList;
import java.util.stream.Collectors;

/**
 * @author lbw
 * @version 1.0
 * @date 2021/10/18 19:15
 */
public class MergeInterval {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        intervals = (ArrayList<Interval>) intervals.stream().sorted(((o1, o2) -> o1.start - o2.start)).collect(Collectors.toList());

        int len = intervals.size();
        int i = 0;
        while (i < len) {
            int left = intervals.get(i).start;
            int right = intervals.get(i).end;
            while (i < len - 1 && intervals.get(i + 1).start <= right) {
                right = Math.max(right, intervals.get(i + 1).end);
                i++;
            }
            res.add(new Interval(left, right));
            i++;
        }
        return res;
    }

    public class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }
}
